package JZ_Offer.dataStructure.list;

import base.ListNode;

/**
 * 链表中环的入口结点
 * <p>
 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
 */
public class JZ23_链表中环的入口结点 {

    /**
     * 1.判断链表中有环 -> 2.得到环中节点的数目 -> 3.找到环中的入口节点
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;

        // 1 判断链表中有环
        boolean circle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                circle = true;
                break;
            }
        }

        if (!circle) {
            return null;
        }

        // 2 得到环中节点的数目
        int count = 1;
        fast = fast.next;
        while (slow != fast) {
            fast = fast.next;
            count++;
        }

        // 3 找到环中的入口节点
        slow = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    /**
     * 快慢指针。快指针一次走两步，慢指针一次走一步，设链表起点到入口结点的长度是x1，快慢指针第一次相遇时距离入口结点的长度是x2，此时慢指针走了x1+x2，快指针走了2x1+2x2，也就是说x1+x2的长度正好是环的一圈大小的倍数。
     * 此时让一个指针从起点出发，一个指针从相遇结点出发，都是一次走一步，当两个指针第一次相遇时恰好是在入口结点。
     */
    public ListNode EntryNodeOfLoop1(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;

        boolean circle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                circle = true;
                break;
            }
        }

        if (circle) {
            ListNode index1 = pHead;
            ListNode index2 = slow;
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }

        return null;
    }

}
